package cn.wit.testalgorithms;

import java.util.Arrays;

/**
 * 最长公共子前缀
 * 
 * @author 16604
 *
 */
public class DemoLongestCommonPrefix {
	public static void main(String[] args) {

//		String[] s = { "flower", "flow", "flight" };
		String[] s= {"dog","racecar","car"};
//		String[] s= {};
		

		// System.out.println(s.length);

		System.out.println(longestCommonPrefix(s));
	}

	public static String longestCommonPrefix(String[] strs) {

		
		//边界判断
		if(strs.length==0) {
			return "";
		}
		
		for(int i=0;i<strs.length-1;i++) {
			if(strs[i].length()<strs[i+1].length()) {
				String s=strs[i];
				strs[i]=strs[i+1];
				strs[i+1]=s;
			}
		}
		
		System.out.println(Arrays.toString(strs));
//		Arrays.sort(strs);
		// 定义一个字符串，用来接受公共字符串
		StringBuilder sb = new StringBuilder();

		// 就先假设第一个字符串就是最长公共前缀
		sb.append(strs[strs.length-1]);
//		System.out.println(strs[1]);

		// System.out.println(sb);
//		System.out.println(strs[1].length());
//		System.out.println(strs[1].charAt(3));

		/*
		 * 接下来去比较剩下来的字符串，相同就不变，不同就减少 出现不同后，就不看后面的呢，从不同的地方截断 接着去比较下一个字符串
		 */
		for(int i =0;i<strs.length-1;i++) {
			
			//特别注意这里的循环判断条件是sb.length
			for(int j=0;j<sb.length();j++) {
				if(sb.charAt(j)!=strs[i].charAt(j)) {
					sb.delete(j, sb.length());
				}
			}
		}
		if(sb.length()==0) {
			return "";
		}
		

		return sb.toString().toLowerCase();
	}

}
